package com.wp.dataStructure.树;

import java.util.Stack;

/**
 * Created by 王萍 on 2017/3/8 0008.
 */
public class BinaryTree {

    private TreeNode root;

    public BinaryTree() {
        this.root = new TreeNode(1, "rootNode(A)");
    }

    public void createBinaryTree(TreeNode root) {
        TreeNode node2 = new TreeNode(2, "静态代码块静态变量构造代码块的执行顺序");
        TreeNode node3 = new TreeNode(3, "C");
        TreeNode node4 = new TreeNode(4, "D");
        TreeNode node5 = new TreeNode(5, "E");
        TreeNode node6 = new TreeNode(6, "F");

        root.setLeftChild(node2);
        root.setRightChild(node3);
        root.getLeftChild().setLeftChild(node4);
        root.getLeftChild().setRightChild(node5);
        root.getRightChild().setRightChild(node6);
    }

    public boolean isEmpty() {
        return root == null;
    }

    public int height() {
        return height(root);
    }

    public int height(TreeNode root) {
        if (root==null) return 0;
        else {
            int leftSize = height(root.getLeftChild());
            int rightSize = height(root.getRightChild());
            return (leftSize < rightSize) ? rightSize + 1 : leftSize + 1;
        }
    }

    public int size(TreeNode root) {
        if (root==null) return 0;
        else {
            return 1 + size(root.getLeftChild()) + size(root.getRightChild());
        }
    }

    public TreeNode parent(TreeNode subTree, TreeNode node) {
        if (subTree == null)
            return null;
        if (subTree.getLeftChild() == node || subTree.getRightChild() == node) return subTree;
        //在左子树上寻找
        TreeNode parent = parent(subTree.getLeftChild(), node);
        if (parent != null) return parent;
            //在右子树上找
        else return parent(subTree.getRightChild(), node);
    }

    public TreeNode parent(TreeNode node) {
        return (root == null || root == node) ? null : parent(root, node);
    }

    public TreeNode getRoot() {
        return root;
    }

    public void destroy(TreeNode subTree) {
        if (subTree != null) {
            destroy(subTree.getLeftChild());
            destroy(subTree.getRightChild());
            subTree = null;
        }
    }

    public void traverse(TreeNode subTree) {
        System.out.println("key:" + subTree.getKey() + "   value:" + subTree.getData());
        traverse(subTree.getLeftChild());
        traverse(subTree.getRightChild());
    }

    public void visited(TreeNode subNode) {
        subNode.setVisited(true);
        System.out.println("key:" + subNode.getKey() + "--name:" + subNode.getData());
    }

    public void preOrder(TreeNode subTree) {
        if (subTree != null) {
            visited(subTree);
            preOrder(subTree.getLeftChild());
            preOrder(subTree.getRightChild());
        }
    }

    public void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.getLeftChild());
            visited(node);
            inOrder(node.getRightChild());
        }
    }

    public void afterOrder(TreeNode node) {
        if (node != null) {
            afterOrder(node.getLeftChild());
            afterOrder(node.getRightChild());
            visited(node);
        }
    }

    //前序遍历的非递归实现
    public void nonRecPreOrder(TreeNode p) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = p;
        while (node != null || stack.size() > 0) {
            while (node != null) {
                visited(node);
                stack.push(node);
                node = node.getLeftChild();
            }
            while (stack.size() > 0) {
                node = stack.pop();
                node = node.getRightChild();
            }
        }
    }

    //中序遍历的非递归实现
    public void nonRecInOrder(TreeNode p) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = p;
        while (node != null || stack.size() > 0) {
            //存在左子树
            while (node != null) {
                stack.push(node);
                node = node.getLeftChild();
            }
            //栈非空
            if (stack.size() > 0) {
                node = stack.pop();
                visited(node);
                node = node.getRightChild();
            }
        }
    }

    //后序遍历的非递归实现
    public void noRecPostOrder(TreeNode p) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = p;
        while (p != null) {
            //左子树入栈
            for (; p.getLeftChild() != null; p = p.getLeftChild()) {
                stack.push(p);
            }
            //当前结点无右子树或右子树已经输出
            while (p != null && (p.getRightChild() == null || p.getRightChild() == node)) {
                visited(p);
                //纪录上一个已输出结点
                node = p;
                if (stack.empty())
                    return;
                p = stack.pop();
            }
            //处理右子树
            stack.push(p);
            p = p.getRightChild();
        }
    }

    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        bt.createBinaryTree(bt.root);
        System.out.println("the size of the tree is " + bt.size(bt.root));
        System.out.println("the height of the tree is " + bt.height());

        System.out.println("*******(前序遍历)[ABDECF]遍历*****************");
        bt.preOrder(bt.root);

        System.out.println("*******(中序遍历)[DBEACF]遍历*****************");
        bt.inOrder(bt.root);

        System.out.println("*******(后序遍历)[DEBFCA]遍历*****************");
        bt.afterOrder(bt.root);

        System.out.println("***非递归实现****(前序遍历)[ABDECF]遍历*****************");
        bt.nonRecPreOrder(bt.root);

        System.out.println("***非递归实现****(中序遍历)[DBEACF]遍历*****************");
        bt.nonRecInOrder(bt.root);

        System.out.println("***非递归实现****(后序遍历)[DEBFCA]遍历*****************");
        bt.noRecPostOrder(bt.root);
    }
}
































